package cn.kent.simple;

/**
 * 367. 有效的完全平方数
 */
public class IsPerfectSquare {

    /**
     * 牛顿迭代法
     * 时间复杂度：O(log(n))
     * 空间复杂度：O(1)
     */
    public static boolean isPerfectSquare3(int num) {
        double x0 = num;
        while (true) {
            Double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }

    /**
     * 二分查找
     * 注意：强转一次long，如果不强转，会报错，因为存在可能超过 {@link Integer#MAX_VALUE} 的值
     */
    public static boolean isPerfectSquare2(int num) {
        int l = 1, r = num;
        while (l <= r) {
            int m = l + (r - l) / 2;
            long square = (long) m * m;
            if (square == num) return true;
            else if (square < num) l = m + 1;
            else r = m - 1;
        }
        return false;
    }

    /**
     * 使用工具方法
     * -  底层使用pow函数，so->时空复杂度与 CPU 支持的指令集相关
     */
    public static boolean isPerfectSquare1(int num) {
        int x = (int) Math.sqrt(num);
        return x * x == num;
    }

    /**
     * 暴力破解法
     * 时间复杂度：O(根号n) 最多需要遍历 根号n+1个正整数
     * 空间复杂度：O(1)
     */
    public static boolean isPerfectSquare(int num) {
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (i * i == num) {
                return true;
            } else if (i * i > num) {
                return false;
            }
        }
        return false;
    }
}
